package com.atwy.search;

/**
 * 二分查找，针对有序
 * 有相同元素时，可将下标集合放到 List中
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {2, 3, 5, 9, 12, 34, 65};
        int index = search(array, 5);

        if (index == -1) {
            System.out.println("没有找到到");
        } else {
            System.out.println("找到，下标为=" + index);
        }
    }

    public static int search(int[] array, int target) {
        if (array == null || array.length < 1) {
            return -1;
        }
        // 1.首先找到数组的中间的下标 mid = (left + right)/2
        // 2.然后让需要查找的数target与array[mid]比较
        // 2.1 如果target 大，说明要查找的数在数组mid位置的右边
        // 2.2 如果target 小，说明要查找的数在数组mid位置的左边
        // 3.递归进行，找到或者遍历结束停止
        return binarySearch(array, 0, array.length - 1, target);
    }

    private static int binarySearch(int[] array, int left, int right, int target) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midValue = array[mid];

        if (target > midValue) {// 往右递归
            return binarySearch(array, mid + 1, right, target);
        } else if (target < midValue) {// 往左递归
            return binarySearch(array, 0, mid - 1, target);
        } else {
            return mid;
        }
    }
}
